1. Field of the Invention
The present invention is directed to a system that performs a multi-dimensional interpolation typically used in color processing and, more particularly, one in which the sequence of the interpolation is governed by a ranking of the fractional parts of the point or value to be interpolated.
2. Description of the Related Art
Current color management techniques are based on the use of color transforms that include multi-dimensional xe2x80x9cgridxe2x80x9d tables to embody a given color mapping. When processing pixel data through a color transform or when composing or combining transforms it is necessary to interpolate in the N-dimensional tables (where N is the number of input dimensions) because storing the value of the mapping for every possible input would lead to impractically large data structures. Kodak""s color management module or CMM uses a linear interpolation technique to interpolate in the grid tables. A linear method can give good quality and speed characteristics. The high evaluation speed is partly a consequence of the fact that only N+1 grid points are required to perform an interpolation (other techniques such as trilinear require more points, 2{circumflex over ( )}N in the case of trilinear or its higher dimensional equivalents). However, achieving the fastest evaluation speed also requires a good algorithm for determining which N+1 points to use (out of the possible 2{circumflex over ( )}N in the surrounding hypercube) and determining which coefficients to use in performing the interpolation.
What is needed is a technique to determine the sequence in which coefficients are selected for interpolation.
Current linear interpolations give acceptable performance when N=4 but degrade quickly as the number of input dimensions increases. However, transformations involving more than 4 input dimensions are gradually becoming necessary. For example, processing images originating in a space designed for xe2x80x9cHi-Fixe2x80x9d printing requires between 5 and 8 input dimensions corresponding to the number of inks used.
What is needed is a technique that allows an arbitrarily high number of dimensions to be involved in interpolation and to provide accurate and fast results in such as situation.
It is an object of the present invention to provide a system that allows an N-dimensional interpolation to be efficiently performed.
It is another object of the present invention to provide a system that does not require large tables or other overhead to determine which grid coefficients or components to use in an interpolation.
It is an additional object of the present invention to provide a technique that determines the sequence of coefficients in the interpolation.
It is also an object of the present invention to provide a system which efficiently chooses which vertices to use for interpolation.
It is a further object of the present invention to provide a process that can be used regardless of the number of input dimensions or output dimensions in the interpolation.
The above objects can be attained by a system that ranks the sequence of grid point interpolations by the fractional components of the point or value to be interpolated. An N-dimensional interpolation is performed according to this sequence.
These together with other objects and advantages, which will be subsequently apparent, reside in the details of construction and operation as more fully hereinafter described and claimed, reference being had to the accompanying drawings forming a part hereof, wherein like numerals refer to like parts throughout.